1. Field of the Invention
The present invention relates to a hash value calculation apparatus and a method thereof.
2. Description of the Related Art
(About Hash Function)
In recent years, since, for example, general home users can connect optical fiber networks with low cost, the infrastructures that support the Internet have been put into place, and communications have been rapidly sped up. Various digital devices can be connected to networks, and communications between digital devices via the Internet are frequently made.
As an indispensable function in such communications between digital devices, authentication of communication partners and messages is demanded in addition to encryption of messages to be exchanged. In this authentication of communication partners and messages between digital devices, an algorithm called a hash function is normally used.
The hash function is an algorithm (function), which inputs a message of an arbitrary bit length and outputs a hash value of a fixed bit length. This hash function calculates a hash value by the following processes.
1) Predetermined data is appended to the rearmost position of an input message of an arbitrary bit length to be an integer multiple of a bit length of a block specified in the algorithm (padding process).
2) The message that has undergone the padding process is extended for respective blocks to generate extended messages (message extension process).
3) A process for changing an internal state value from an initial value using the extended messages (extended blocks) corresponding to blocks is repeated the number of times specified in the algorithm. Note that as the initial value of the internal state value, a predetermined fixed value (to be referred to as a hash initial value hereinafter) which is specified in the algorithm is used for the first block. For the second and subsequent blocks, a hash intermediate value (to be described later) for a block immediately before the block of interest is used (step process).
4) An internal state value after the step processes for the predetermined number of times is added to this addition process result for the immediately preceding block (to be referred to as a hash intermediate value hereinafter) to calculate a new hash intermediate value. Note that for the first block, an internal state value after the step processes for the predetermined number of times is added to a hash initial value to calculate a hash intermediate value (addition process).
5) The processes 2) to 4) are sequentially executed for all blocks. A hash intermediate value obtained upon completion of the processes of all extended messages is output as a hash value.
A combination of the processes 1) to 5) of the hash function will be referred to as a hash value calculation. Note that the processes 3) and 4) of the hash function for a certain block can be executed if the hash initial value is available for the first block or if the hash intermediate value of the immediately preceding block is available for the second and subsequent blocks. Therefore, the hash value calculation is interrupted when a hash intermediate value from the first block to a certain block is calculated, and the process from the next block can be resumed using that hash intermediate value.
There are the following three principal features of the hash function. As the first feature, a hash value can be calculated from a message, but it is practically impossible to calculate back an input message from an output hash value (one-way). As the second feature, when a hash value of a certain message is given, it is very difficult to find out another message having that hash value (weak collision resistance). As the third feature, it is very difficult to find out two different messages whose hash values match (strong collision resistance).
The hash function having such properties is used in various communication protocols such as SSL/TLS and IPSec. A hash function algorithm that can be used is determined by the specification for each communication protocol. In communications between digital devices, a hash algorithm installed in both the digital devices is selected from those which can be used in communication protocols adopted by the digital devices, and is used in an authentication process.
As communications are sped up, needs to guarantee the communication speed in encryption communications are increasing, and required response times are different depending on data to be processed. For example, a long response time of the hash value calculation to some extent is allowed for large-capacity image data for alteration detection. However, a very short response time of the hash value calculation is expected for a short password required for personal authentication. Therefore, it is also demanded for the hash value calculation to speed up the processes and to shorten a response time for data with high priority as much as possible. It is indispensable to implement processes by hardware to speed up the hash value calculation. In case of hardware implementation, since the circuit scale directly relates to cost, one hardware resource such as a hash value calculation circuit that implements the hash value calculation is prepared per system, and the hash value calculations for a plurality of messages are implemented by sharing the one hardware resource.
As described above, the hash value calculation divides a message of an arbitrary bit length into blocks each having a fixed bit length, and processes these blocks. Upon completion of the hash value calculations for all blocks, a hash value for that message can be obtained.
(Switching of Message to be Processed)
A case will be examined below wherein under the condition that the hash value calculations for a plurality of messages are executed using one hardware resource, after the hash value calculation for a very long message starts, a hash processing request for a short message with high priority is received. In such a case, the hash value calculation for the first message requires a lot of time, and a given response time cannot be guaranteed in association with the hash value calculation for the short message with high priority. Hence, in order to guarantee a given response time, a mechanism for speeding up the hash value calculation itself, assigning priority levels to messages to be processed, and processing a message with high priority first is required. For example, the following mechanism is required. That is, the hash value calculation of the long message which is input first is temporarily interrupted, that for the short message with high priority is executed first, and after completion of the process for the short message, the hash value calculation for the long message is resumed.
Conventionally, an encryption processing apparatus which can efficiently interrupt and resume an encryption process such as a hash value calculation independently of various encryption algorithm differences and encryption process mode differences is known (Japanese Patent Laid-Open No. 2006-39000). In this arrangement, a descriptor of a DMA controller includes a format that instructs to interrupt and resume a hash value calculation. When a message is transferred while being appended with interrupt information, an internal state value stored as the calculation result of the hash value calculation up to a certain block in the middle of the message is written out to an external memory. On the other hand, when a message is transferred while being appended with resume information, the internal state value stored in the external memory is read out, and the hash value calculation is resumed from the next block in the message.
(Support of Plural Hash Functions)
On the other hand, hash algorithms that can be used in encryption communication protocols are respectively prescribed. In communications between digital devices, a hash algorithm that can be commonly executed by both communication devices is selected from those installed in the respective communication devices. Hash algorithms that can be executed by partner communication devices may often be different, and a device which is required to make encryption communications with many communication devices has to execute many different hash algorithms.
Furthermore, in recent years, the vulnerability of SHA-1 and MD5, which have been popularly used as the standards of hash algorithms, has been pointed out, and a transition to hash algorithms with higher security, which are generically named as SHA-2, is recommended. Even in standard encryption communication protocols, it is presumed to adopt hash algorithms with a multi-bit length such as SHA-2 in the near future. However, new products can adopt new hash algorithms, but there are many digital devices which support only old hash algorithms and are difficult to undergo running changes. Therefore, both old hash algorithms which have been conventionally used as standards, and new hash algorithms with high security have to be supported so as to make secure communications with various digital devices. Japanese Patent Laid-Open No. 2004-53716 discloses a hash function processing circuit which implements a plurality of hash functions as hardware.
In case of a hash value calculation circuit which sequentially executes hash value calculations for respective messages, when the hash value calculation for a certain message starts, that for another message has to wait for completion of this hash value calculation. When the currently processed message is very long, and another waiting message is very short, the processing performance within a predetermined response time for all messages cannot be guaranteed. In order to solve such problem, it is desired to provide a mechanism that can simultaneously process a message during processing of another message.
(Problems About Switching of Message to be Processed)
However, in the arrangement of Japanese Patent Laid-Open No. 2006-39000, data stored as an intermediate arithmetic result of the hash value calculation is an internal state value before the addition process, and a hash intermediate value after the addition process required to resume the hash value calculation is not stored. Therefore, only this arrangement cannot actually resume the hash value calculation. In order to interrupt and resume the hash value calculation, a hash intermediate value of the immediately preceding block has to be separately stored in addition to the aforementioned arrangement. Alternatively, in order to generate a hash intermediate value of the immediately preceding block, a hash intermediate value of a block before the immediately preceding block has to be separately stored, and has to be added to an internal state value stored in the external memory. In this manner, in the framework of the conventional arrangement, the amount of data to be stored increases, and a temporal overhead about the addition process also increases.
With an arrangement by adding a hash intermediate value storing or generating apparatus to the arrangement of Japanese Patent Laid-Open No. 2006-39000, hash value calculations may be executed by switching a plurality of messages in the middle of processing. However, with this arrangement, of a plurality of blocks which form a message, a hash value calculation intermediate value up to an intermediate block is written out to the external memory to interrupt the process, and is read out from the external memory upon resuming the process. For this reason, an extra time is required to read/write the hash value calculation intermediate value from/in the memory.
For example, the bit length of a hash intermediate value amounts to 160 bits for SHA-1, 256 bits for SHA-256, and 512 bits for SHA-512. Memory read/write accesses are normally made in 32-bit or 64-bit units, and the intermediate arithmetic result of the hash value calculation is written in or read out from the memory to require several to several ten cycles. Since the memory read/write accesses of data further require an extra time such as a waiting time required to assure the bus right, a large temporal overhead other than the hash value calculation itself is required to interrupt and resume the hash value calculation based on the aforementioned related art.
When the hash value calculations for a plurality of messages are switched in the middle of the processing in the above arrangement, an internal state value obtained as a result of the hash value calculation up to an intermediate block in the hash value calculation for one message has to be written in the external memory connected to a bus. However, leaking the internal state value outside a hash value calculator means an increase in risk of theft, thus posing a security problem.
Upon interrupting and resuming the hash value calculation, it is desired to reduce read/write overheads of not only the intermediate arithmetic result of the hash value calculation, but also the message itself on the external memory. For example, in case of SHA-1, the bit length of a block as a processing unit of a message is 512 bits, and memory read/write accesses in 32-bit or 64-bit units require 16 or 8 cycles. When the hash value calculation is applied to data of blocks of a new message or to blocks of a temporarily discarded message, a time required to read out the blocks of the message from the external memory imposes a large overhead of the hash value calculation.
As described in Japanese Patent Laid-Open No. 2006-39000, the descriptor format of the DMA controller which can give the instruction to interrupt and resume the hash value calculation is provided to eliminate the intervention of software required to make condition determination at the time of interrupt/resume control, thus efficiently interrupting and resuming the hash value calculation. However, Japanese Patent Laid-Open No. 2006-39000 discloses only a technique in which after a CPU recognizes in advance a part to be interrupted and resumed of data of a message before transfer of data to the hash value calculator, the CPU transfers that data to the hash value calculator together with information indicating the presence/absence of interruption/resuming. That is, this reference does not disclose any technique for interrupting and resuming processing of a message after a hash processing request for data of the message is temporarily issued to the hash value calculator.
(Problem about Support of Plural Hash Functions)
In case of hardware implementation to speed up the hash value calculation, not only hash algorithm circuits but also storage units which respectively store data that has undergone the message extension process, data that has undergone the step process, and data that has undergone the addition process are required. The circuit scale increases when hardware components which process many different hash algorithms and a new hash algorithm with high security are respectively arranged. Especially, the new hash algorithm with high security requires a larger-capacity storage unit since the bit length of its hash value is large. However, the circuit scale of the hardware is required to be suppressed as much as possible so as to generally attain power and cost savings.
A conventional hash apparatus includes a plurality of dedicated circuits which process different hash algorithms, and a storage unit which is commonly used by these plurality of dedicated circuits, and executes a hash value calculation by selecting one of the hash algorithms. In this case, since the plurality of hash algorithms commonly use the storage unit, it is impossible to simultaneously execute hash value calculations for a plurality of messages, and the processing performance within a predetermined response time for all messages consequently cannot be guaranteed.
As in the arrangement described in Japanese Patent Laid-Open No. 2004-53716, a plurality of dedicated circuits which process different hash algorithms are arranged, and only a dedicated circuit corresponding to the requested hash algorithm is operated. However, in this case, not only the circuit scale increases considerably, but also variations of consumption power of the entire hash value calculation apparatus become large. Hence, it becomes easy to externally analyze internal information of the circuit by power analysis. For this reason, such arrangement is not preferable also in terms of tamper resistance (security).